/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

import leetCode.killProcess.Node;

/**
 * @author zhongfang
 *
 */
public class killProcess {
	class Node{
		int id;
		ArrayList<Node> childs=new ArrayList<>();
	}
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        List<Integer> result=new ArrayList<>();
        HashMap<Integer,Node> nodes=new HashMap<>(pid.size());
        nodes.putIfAbsent(1, null);
        for (int i = 0; i < pid.size(); i++) {
        	int curId=pid.get(i);
        	int parentId=ppid.get(i);
        	Node paNode = null,curNode = null;
        	curNode=getNode(nodes, curId);
        	if(parentId!=0){
        		paNode=getNode(nodes, parentId);
	        	paNode.childs.add(curNode);
        	}
		}
        Node curNode=nodes.get(kill);
        int toDealIndex=0;
        result.add(curNode.id);
        while (toDealIndex<result.size()) {
			curNode=nodes.get(result.get(toDealIndex));
			toDealIndex++;
			for (Node nextNode : curNode.childs) {
				result.add(nextNode.id);
			}
		}
        return result;
    }
    private Node getNode(HashMap<Integer, Node> nodes, int curId) {
    	if(nodes.containsKey(curId)){
    		return nodes.get(curId);
    	}else {
			Node curNode=new Node();
			curNode.id=curId;
			nodes.put(curId, curNode);
			return curNode;
		}
	}
	public static void main(String[] args) {
		int[] pID={1, 3, 10, 5};
		int[] ppID={3, 0, 5, 3};
		killProcess killProcess=new killProcess();
		ArrayList<Integer> pList=killProcess.toList(pID);
		ArrayList<Integer> ppList=killProcess.toList(ppID);
		List<Integer> rIntegers=killProcess.killProcess(pList, ppList, 5);
		System.out.println(rIntegers);
	}
	private ArrayList<Integer> toList(int[] pID) {
		ArrayList<Integer> result=new ArrayList<>(pID.length);
		for (Integer integer : pID) {
			result.add(integer);
		}
		return result;
	}
}
